package leetcode;

public class DivideTwoIntegers {

	public static void main(String[] args) {
		DivideTwoIntegers object = new DivideTwoIntegers();
//		System.out.println(object.multiply(-59, -15));
		System.out.println(object.divide(Integer.MIN_VALUE, 1));
	}
	
	//首先我们得弄清楚乘法是怎样的
	//计算机可以将一个数表示成X = sum(2 ^ ni)(对于int而言 i从0 ~ 32)
	//那么计算X * a 的时候，我们先以十进制说明
	//X * a = X * a的最高位 * 10^最高位的位数 + X * a的次高位 * 10^次高位的位数 + ... + X * a的最低位 * 10^最低位的位数
	//对于二进制而言，是一样的：X * a = sum(X * ni * 2^i) i表示是第几位，ni表示该位是1还是0
	
	public int multiply(int a, int b){
		boolean positive = true;
		if(b < 0){
			positive = false;
			b = -b;
		}
		int total = 0;
		int length = getLength(b);
		
		for(int i = 0; i < length; i++){
			if(getIndexBit(b, i) == 1){
				total += a << i;
			}
		}
		return positive ? total : -total;
	}
	
	public int getLength(long num){
		int res = 0;
		while(num != 0){
			num >>>= 1;
			res++;
		}
		return res;
	}
	
	public int getIndexBit(int num, int pos){
		//获取从右到左的第pos位置的值 1 / 0
	    return (num >>> pos) & 1;
	}
	
	
	//除法
	public int divide(int dividend, int divisor) {
        if(divisor == 0){
            if(dividend != 0){
                throw new ArithmeticException("divide by zero");
            }else{
                return 0;
            }
        }
        if(dividend == 0){
            return 0;
        }
        //什么情况会overflow,就是被除数为MIN, divisor为-1
        if(dividend == Integer.MIN_VALUE && divisor == -1){
            return Integer.MAX_VALUE;
        }
        
        if(divisor == Integer.MIN_VALUE){
        	if(dividend == Integer.MIN_VALUE){
        		return 1;
        	}else{
        		return 0;
        	}
        }
        
        //有一个问题，这是对于都是正数时候的计算，但我们知道负数的范围要比正数大1
        //所以我们将正的转换为负的
        //好吧，将数转为负的就不能使用这种方法了
        long longDividend = dividend;
        if(dividend < 0){
        	if(dividend == Integer.MIN_VALUE){
        		longDividend = -(long)dividend;
        	}else{
        		longDividend = -dividend;
        	}
        }
        
        //如果被除数的绝对值小于除数，那么返回0
        if(Math.abs(longDividend) < Math.abs(divisor)){
        	return 0;
        }
        
        boolean negative = false;
        if(dividend < 0 && divisor > 0 || dividend > 0 && divisor < 0){
            negative = true;
        }
        
        //除数要保持是正的
        if(divisor < 0){
        	divisor = -divisor;
        }
        
        //接下来我们按照计算除法的规则进行，当该位小于除数时，该位填0，然后与下一位联合，判断此时的商...
        int length = getLength(longDividend);
        int length2 = getLength(divisor);
        long cur = getFirst(longDividend, length, length2);
        long res = 0;
        for(int i = length2 - 1; i < length;){
        	res = (res << 1);
        	if(cur >= divisor){
        		res += 1;
        		cur = combine(longDividend, length, cur - divisor, ++i);
        	}else{
        		res += 0;
        		cur = combine(longDividend, length, cur, ++i);
        	}
        }
        
        return negative ? (int)-res : (int)res;
    }
	
	//首先得到被除数的前length位
	public long getFirst(long nums, int length, int desireLength){
		long res = 0;
		int temp = length - desireLength;
		for(int i = length - 1; i >= temp; i--){
			res = (res << 1) + ((nums >>> i) & 1);
		}
		return res;
	}
	
	//将nums的position位连接到cur后面
	//position表示从左到右
	public long combine(long nums, int length, long cur, int position){
		if(position == length){
			return 0;
		}
		int move = length - 1 - position;
		return (cur << 1) + ((nums >>> move) & 1);
	}
	
	
	//不使用long来避免溢出
	public int divideWithoutLong(int dividend, int divisor) {
		if(dividend==Integer.MIN_VALUE && divisor==-1) return Integer.MAX_VALUE;
        if(dividend > 0 && divisor > 0) return divideHelper(-dividend, -divisor);
        else if(dividend > 0) return -divideHelper(-dividend,divisor);
        else if(divisor > 0) return -divideHelper(dividend,-divisor);
        else return divideHelper(dividend, divisor);
    }
    
    private int divideHelper(int dividend, int divisor){
        // base case
        if(divisor < dividend) return 0;
        // get highest digit of divisor
        int cur = 0, res = 0;
        while((divisor << cur) >= dividend && divisor << cur < 0 && cur < 31) cur++;
        res = dividend - (divisor << cur-1);
        if(res > divisor) return 1 << cur-1;
        return (1 << cur-1)+divide(res, divisor);
    }
}
